Bi-directional search is a widely used strategy to increase the success andconvergence rates of sampling-based motion planning algorithms. Yet, fewresults are available that merge both bi-directional search and asymptoticoptimality into existing optimal planners, such as PRM*, RRT*, and FMT*. Theobjective of this paper is to fill this gap. Specifically, this paper presentsa bi-directional, sampling-based, asymptotically-optimal algorithm namedBi-directional FMT* (BFMT*) that extends the Fast Marching Tree (FMT*)algorithm to bi-directional search while preserving its key properties, chieflylazy search and asymptotic optimality through convergence in probability. BFMT*performs a two-source, lazy dynamic programming recursion over a set ofrandomly-drawn samples, correspondingly generating two search trees: one incost-to-come space from the initial configuration and another in cost-to-gospace from the goal configuration. Numerical experiments illustrate theadvantages of BFMT* over its unidirectional counterpart, as well as a number ofother state-of-the-art planners.
展开▼
